package org.algorithm.YaYa.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;

/**
 * @Date 2022/2/27
 * @Link {https://leetcode-cn.com/problems/merge-k-sorted-lists/}
 */
public class 合并K个升序链表 {

    @Test
    public void test(){
        ListNode listNode1 = ListNode.build(1, 5, 7);
        ListNode listNode2 = ListNode.build(1, 2, 6);
        ListNode node = mergeKLists(new ListNode[]{listNode1, listNode2});
        System.out.println(ListNode.print(node));
    }

    
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (true) {
            ListNode minNode = null;
            int minPointer = -1;
            for (int i = 0; i < k; i++) {
                if (lists[i] == null) {
                    continue;
                }
                if (minNode == null || lists[i].val < minNode.val) {
                    minNode = lists[i];
                    minPointer = i;
                }
            }
            if (minPointer == -1) {
                break;
            }
            tail.next = minNode;
            tail = tail.next;
            lists[minPointer] = lists[minPointer].next;
        }
        return dummyHead.next;
    }




}
